package search

import (
	pos "code.google.com/p/gochess/position"
	stats "code.google.com/p/gochess/statistics"
)

func init() {
	Transpositions = newTranspositionTable(TTDefaultSize)
	// init statistics
	stats.FilledBuckets = make([]stats.Value, buckets)
	stats.RestoredBuckets = make([]stats.Value, buckets)
}

type nodeType uint32

const (
	invalidNodeType nodeType = iota
	allNode
	cutNode
	pVNode
)

var nodeTypes = [4]string{
	invalidNodeType: "invalid node type",
	allNode:         "All node",
	cutNode:         "Cut node",
	pVNode:          "PV node"}

func (this nodeType) String() string {
	return nodeTypes[this]
}

const (
	bitSizeDepth = 8
	bitMaskDepth = 1<<bitSizeDepth - 1

	bitSizeNodeType = 2
	bitMaskNodeType = 1<<bitSizeNodeType - 1

	bitOffsetNodeType = bitSizeDepth
	bitOffsetMove     = bitOffsetNodeType + bitSizeNodeType
	bitOffsetScore    = bitOffsetMove + pos.BitSizeMove
)

var Transpositions *TranspositionTable

type transposition int64

func (this transposition) Depth() int32 {
	return int32(this & bitMaskDepth)
}

func (this transposition) NodeType() nodeType {
	return nodeType(this >> bitOffsetNodeType & bitMaskNodeType)
}

func (this transposition) Move() pos.Move {
	return pos.Move(this >> bitOffsetMove & pos.BitMaskMove)
}

func (this transposition) Score() int32 {
	return int32(this >> bitOffsetScore)
}

const buckets = 4

// Default size of TT in MegaBytes
const TTDefaultSize = 64

type TranspositionTable struct {
	full    int
	entries [][buckets]transpositionInfo
}

type transpositionInfo struct {
	hash zobristHash
	/*	Depth: 1-8 (0-256)
		NodeType: 9-10 (0-3)
		Move: 11-32
		Score: 33-63	*/
	info transposition
}

// Size of an Transposition table entry in byte
const entrySize = 2 * 8

// size is in MB
func newTranspositionTable(size int) *TranspositionTable {
	tt := &TranspositionTable{}
	tt.Resize(size)
	return tt
}

func (tt *TranspositionTable) Resize(size int) {
	newLen := roundDownToPowerOf2(size * 1024 * 1024 /
		(buckets * entrySize))
	if len(tt.entries) != newLen {
		tt.entries = make([][buckets]transpositionInfo, newLen)
	}
}

// ligthweight way to change tt size, for testing
func (tt *TranspositionTable) setLen(size int) {
	if len(tt.entries) != size {
		tt.entries = make([][buckets]transpositionInfo, size)
	}
}

func (this *TranspositionTable) get(hash zobristHash) transposition {

	stats.HashGetRequests++
	entrySet := &this.entries[int(hash)&(len(this.entries)-1)]
	for i := range entrySet {
		if entrySet[i].hash == hash {
			stats.RestoredBuckets[i]++
			return entrySet[i].info
		}
	}
	return 0
}

func (tt *TranspositionTable) Clear() {
	for i := range tt.entries {
		for j := 0; j < buckets; j++ {
			tt.entries[i][j].hash = 0
		}
	}
}

// Filled returns filling level of the table in permill.
func (tt *TranspositionTable) Filled() int {
	return (tt.full * 1000) / (len(tt.entries) * buckets)
}

func (this *TranspositionTable) save(hash zobristHash, move pos.Move,
	score, depth int32, nodeType nodeType) {

	stats.WrittenHashes++
	entrySet := &this.entries[int(hash)&(len(this.entries)-1)]
	// search for same hash (=same position) in tt and see if
	// the new information is better, so we can save it
	for i := range entrySet {
		if entrySet[i].hash == hash {
			// found same position, check if new information is better
			if depth >= entrySet[i].info.Depth() {
				stats.OverwrittenSameHashes++
				stats.OverwrittenHashes++
				entrySet[i].info = transposition(depth) | transposition(nodeType)<<bitOffsetNodeType |
					transposition(move)<<bitOffsetMove | transposition(score)<<bitOffsetScore
			}
			return
		}
	}

	// we have a unknown position, search for empty bucket
	// search for bucket with min depth as well, because this
	// is the replacement candidate if there is no empty bucket
	var minDepth, minDepthBucket int32 = 1<<31 - 1, 0
	var i int32
	for i = 0; i < buckets; i++ {
		if entrySet[i].hash == 0 {
			break
		}
		if entrySet[i].info.Depth() < minDepth {
			minDepth = entrySet[i].info.Depth()
			minDepthBucket = i
		}
	}
	if i == buckets {
		this.full--
		stats.AllBucketsFull++
		stats.OverwrittenHashes++
		// no empty bucket, replace bucket with lowest depth
		i = minDepthBucket
		stats.FilledBuckets[i]-- // fix statistics
	}
	this.full++
	stats.FilledBuckets[i]++
	entrySet[i].hash = hash
	entrySet[i].info = transposition(depth) | transposition(nodeType)<<bitOffsetNodeType |
		transposition(move)<<bitOffsetMove | transposition(score)<<bitOffsetScore
}

func probePosition(tp transposition, alpha, beta, depth int32) (bool, int32) {

	if tp.Depth() >= depth {
		nodeType := tp.NodeType()
		score := tp.Score()
		if nodeType == cutNode && score >= beta {
			return true, beta
		}
		if nodeType == allNode && score <= alpha {
			return true, alpha
		}
		if nodeType == pVNode {
			return true, score
		}
	}
	return false, 0
}

func roundDownToPowerOf2(value int) int {

	result := 1
	for ; result <= value; result <<= 1 {
	}
	return result >> 1
}
